package com.lss.d_substr;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lss
 * @description
 * @createDate 2024/12/4-8:38
 * @tag 前缀和
 */
public class lc_560 {
    public static void main(String[] args) {
        int[] nums = {0,0,0,1,2,3};
        int k = 0;
        System.out.println(subarraySum(nums, k));
    }

    /**
     * 查询出在一个数组中连续子数组的和为k的个数
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        // 前缀和
        int[] prefixes = new int[nums.length + 1];
        for (int i = 1; i < prefixes.length; i++) {
            prefixes[i] = nums[i - 1] + prefixes[i - 1];
        }
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 存储前缀和
        map.put(0, 1);
        for (int i = 1; i < prefixes.length; i++) {
            int complement = prefixes[i] - k;
            if (map.containsKey(complement)) {
                ans += map.get(complement);
            }
            // 应对全为0的情况
            map.put(prefixes[i], map.getOrDefault(prefixes[i], 0) + 1);
        }

        return ans;
    }

    /**
     * 0000000
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum_0(int[] nums, int k) {
        int len = nums.length;
        int[] prefixSum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            prefixSum[i + 1] = nums[i] + prefixSum[i];
        }

        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>(len + 1); // 设置容量可以快 2ms
        for (int sj : prefixSum) {
            ans += cnt.getOrDefault(sj - k, 0);
//            cnt.compute(sj,(key,v) -> {
//                Integer integer = cnt.get(key);
//                cnt.put(key,integer + 1);
//                return integer;
//            });
            cnt.merge(sj, 1, Integer::sum); // cnt[sj]++
        }
        return ans;
    }

    /**
     * 00000000000
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum_00(int[] nums, int k) {
        int ans = 0;
        int s = 0;
        Map<Integer, Integer> cnt = new HashMap<>(nums.length + 1); // 设置容量可以快 2ms
        cnt.put(0, 1); // s[0]=0 单独统计
        for (int x : nums) {
            s += x;
            ans += cnt.getOrDefault(s - k, 0);
            cnt.merge(s, 1, Integer::sum); // cnt[s]++
        }
        return ans;
    }

}
